Solid Modelling systems play an increasingly important role in the design of manufactured parts and of manufacturing processes. These systems provide users with both interactive design tools which considerably reduce the cost of design activity and also with simulation and analysis tools which shorten the design cycle and improve the quality of the final products and the efficiency of manufacturing processes.
A solid can be described in terms of its boundary as a list of the types, positions, and dimensions of all of the solids' faces. However, such a description is in general too "verbose" for humans, who prefer to design solids in a hierarchical and incremental manner by combining or altering previously defined subsolids. Many such combinations of subsolids are precisely specified through Boolean set theoretic operations. For example, assembling two parts into a single solid can be modelled mathematically as a set theoretic union. Further shape modifications that produce specific geometric features, such as slots, holes and bosses, are often formulated in terms of set theoretic unions and differences between the solid to be modified and simple primitive volumes, such as cylinders or blocks, to be added to or subtracted from the solid.
A solid model is often employed to represent and analyze the geometric effects of certain manufacturing operations such as material removal by milling and drilling. Such geometric effects can also be expressed in terms of set theoretic operators as, for example, the difference between a part and a region swept by a cutter. Applying a sequence of such operations is an effective method of simulating a machining process. Given the trajectory of a cutter, a solid modeller can be used to verify that the cutter does not collide with fixtures, and also to compute how much material is removed during each motion of the cutter. Such an analysis is important for planning efficient and error free manufacturing processes. The analysis requires the ability to compute Boolean set intersections between solids and to check whether such an intersection is empty or not.
Similarly, the probability of being able to assemble several parts can be analyzed with a solid modeller by producing a large number of models of each part to be assembled, according to specified form and position tolerances, and then determining in which cases the models interfere. Generally, two solids are considered to interfere if and only if their set theoretic intersection is a non-empty three dimensional set.
Many applications, including the simulation of machining processes, require a determination as to whether two representations define identical systems. For example, it is important to verify that a solid model obtained by simulating the effect of the metal cutting operations on a piece of stock is identical to a solid model of the finished desired part.
In all of these important applications a solid model, which can represent parts, tools or characterize the effect of manufacturing operations, can be specified by combining subsolids or primitive volumes through set theoretic Boolean operations such as the union, intersection, and difference of sets. Such a solid is represented by a set theoretic Boolean expression which can be efficiently stored within a computer memory in a binary tree representation. FIG. 1 is an illustrative binary tree representation of a solid (1) which is composed of the union of two subsolids (2) and (3). Subsolid (3) is composed of the difference between the block primitive (4) and the cylindrical primitive (5). The form of such a tree is directly obtained by parsing the Boolean expression (2) +((4)-(5)). The root of the tree (solid 1) is associated with the solid defined by the Boolean expression. Internal nodes of the tree correspond to Boolean operations and are associated with subsolids. Leaves of the tree are associated with primitive volumes, which often are the intersection of relatively simple algebraic half-spaces, that is, regions of space where a simple polynomial function of three space coordinates has a non-positive value. For example, a ball of radius R centered at the origin is a half-space defined by the function x.sup.2 +y.sup.2 +z.sup.2 -R.sup.2 .ltoreq.0. An arbitrarily positioned and oriented primitive volume can be described in terms of a rigid motion transformation, a combination of a rotation with a translation, and of a congruent primitive volume defined in a convenient local coordinate system. Simple primitive volumes can be represented by their type, such as sphere, cylinder or cone, and by a relatively few intrinsic parameters such as radius, length and apex angle. Such a tree is known as a Constructive Solid Geometry representation, and will be abbreviated hereinafter as CSG.
The positions and dimensions, or intrinsic parameters, of the primitive volumes may be expressed in terms of a few primary parameters which characterize a particular member in an entire family of solids represented by the CSG tree. The resulting parameterized CSG representation can therefore be conveniently used to model, for example, an assembly of parts whose dimensions vary within tolerance limits and thus be employed to model and solve the problems described earlier.
It is often convenient to decompose the design activity into a series of steps that incrementally construct the final solid model either by merging subsolids or by modifying them through the addition of details such as the creation of geometric features, blends, and fillets. However, such a complex process can rarely be accomplished without human error and often becomes a trial-and-error process where the designer goes through each step, checks the result, and makes adjustments if necessary. Such adjustments may be limited to the alteration of the value of a parameter or may require the modification of the structure of the particular CSG tree.
Consequently, the efficiency of the interactive process of designing geometric shapes is heavily dependent on visual verification. The designer must be able to immediately visually inspect on a display device the result of a particular design or adjustment step. Not only should changes to the CSG parameters and structure be reflected immediately on a screen but the designer must further have the capability of rotating the displayed object and zooming on detail in an interactive manner. To be useful, the displayed images must be clear and unambiguous. In this regard, results are enhanced with shaded images in which important shape and orientation information is conveyed by displaying the intensity of light reflected by the faces of the solid. It is noted that the correct modelling of shadows adds realism and visual clues. However, shadow modelling is not generally considered to be essential for designing parts and analyzing manufacturing processes and will not be further discussed herein.
As described above, assembly analysis and simulation of manufacturing processes are based on repetitive detection of solid interferences, which involves testing as to whether an intersection of two solids corresponds to an empty set, and also of differences between solids, which involves testing as to whether a symmetric difference of two solids corresponds to an empty set. These tests cannot be performed by visual inspection in cases where the solids are complex and, even for simple solids, the highly repetitive nature of the analysis makes its automation essential. It is therefore important that the tasks of detecting differences and interferences be performed efficiently and automatically by a computer system.
One problem associated with generating a shaded image from a complicated CSG model is that the process involves a vast amount of calculations and data manipulations. Shading programs that run on general purpose computers perform too slowly for interactive design and their use results in a sub-optimal utilization of the designers' time. Dedicated hardware for performing a portion of the display task is known to be commercially available but is not adequate for processing CSG models. In most cases such dedicated hardware must be further combined with software preprocessing operations, which typically decreases the performance of the dedicated hardware beyond limits acceptable for interactive design.
In order to make more apparent the benefits provided by the invention, there will now be given a description of some known techniques that have been developed for producing shaded images of solid models. As will become apparent, an implementation of these techniques on a general purpose computer results in performance which is inadequate for interactive design. Also described are the deficiencies of known approaches based on special purpose hardware.
Facilities for producing shaded pictures of planar or curved faces are available in graphic workstations that provide a polygon filling technique with Gouraud or Phong shading. Solid modeller software provides a compact description of each face of the solid, for example the coordinates of the corners of a polygon in space, and the workstation paints on a display screen a shaded image of the face. The colors and intensities are chosen to indicate the amount of light that would be reflected by the face, given the user defined position(s) of the light source(s) and the user defined position of the viewpoint in the model space. By changing the position of the viewpoint, the user may, for example, see the back of the displayed object or may zoom in on certain details.
In such a system, the display screen is decomposed into a large number of pixels or image picture elements. To display a shaded image of a face on the screen, those pixels covered by the projection of the face must be colored appropriately. These pixels are determined using a model of the screen in the object space and dividing that screen model into small rectangles, each of which is associated with a pixel of the real screen. As can be seen in FIG. 2 a point of a face "covers", or is viewed through a pixel if, in the model space, the line that joins the corresponding point with the viewpoint intersects the model of the screen at the corresponding rectangle. When a face is displayed, the previous coloration of the covered pixels is discarded. A given pixel may be covered by the projections of several faces of a solid model, however only the visible faces, which are closest to the viewpoint, should be displayed while the "hidden faces" should be eliminated. There are several known techniques for eliminating such hidden faces or surfaces.
In regards to front and back faces and referring to FIGS. 3a-3 d, one technique assumes that a normal at each interior point of a face is oriented towards the outside of the solid. Given a viewpoint, the faces of a model are divided into two disjoint sets, namely a set consisting of front faces and a set consisting of back faces. This division may require splitting some curved faces, such as a sphere, into disjoint subsets. At each point of a front face the normal is pointing towards the viewpoint in that the angle between the normal and a direction towards the viewpoint is less than 90 degrees. At each point on a back face the normal is pointing away from the viewpoint in that the angle between the normal and the direction towards the viewpoint is greater or equal to 90 degrees. In a solid model a back face is not a visible face. For polyhedral models wherein all faces are planar most conventional systems can distinguish between front and back faces automatically and can be instructed to display only the front faces. For a convex solid, each pixel is covered by at most one front face. Consequently, correctly shaded images of convex solids can be obtained by simply displaying the front faces.
However, and as shown in FIG. 4, for non-convex solids the projections on the display screen of several front faces can overlap, and a face being processed may be displayed on the screen even though it is partly or totally hidden by other, previously processed faces.
The simplest method to display only visible faces is to ensure that the visible faces are displayed after the faces which they occlude. For this method, the faces are ordered in such a manner that they can be displayed back to front, as shown in FIG. 4, and thus the visible faces which are closer to the viewpoint than the faces they occlude are displayed last. Such an ordering may be derived from a Binary Space Partition (BSP) tree which is viewpoint independent. However, the construction of a BSP tree is computation intensive and requires a software preprocessing step which may require splitting faces. Thus, this method is not suitable for real-time interactive modelling systems.
To avoid this BSP tree preprocessing step a depth buffer, or z-buffer, may be used to automatically select for each pixel the visible face. In the z-buffer approach each pixel is associated with a storage location within the z-buffer which contains the depth of the currently displayed point, the depth typically being represented as a distance between the viewpoint and the displayed point. For each new point that projects on a given display pixel, the depth of the projecting point is compared to the depth stored in the given pixel's memory location. If the new point is in front, that is, its depth is less than the depth stored in the pixel's memory, the new point is displayed and the pixel's memory is updated to reflect the new point's depth. Otherwise, the new point is ignored in that it lies behind an already displayed point and thus is not visible.
The process by which the depth values of points that project onto pixels is generated for a face is called scan-conversion. These depth values are typically generated in scan-line order using a constant depth increment from one pixel to the next. In the methods described below in relation to the invention, pixels that are not covered by a face are assigned a default depth which is the maximum or the minimum depth representable in the z-buffer, depending on the role played by the face.
This method is illustrated in FIGS. 5a-5d for a plurality of points designated a, b and c. In FIG. 5a the intensity for each pixel is set equal to a background intensity and the distance stored in the z-buffer is initially set equal to infinity or some large number. In FIG. 5b a point "a" is processed. The intensity is made equal to that reflected by the point "a" and the distance stored in the z-buffer of the corresponding pixel is made equal to the distance from the view point to point "a". In FIG. 5c, the point "b" is processed. In that the distance to "b" is less than the distance to "a" the point "b" is displayed and the intensity is made equal to that reflected by point "b". Furthermore, the depth of "b" is stored in the z-buffer memory. In FIG. 5d a point "c" is processed. In that the distance to point "c" along the z-axis is greater than the distance to point "b" currently stored int the z-buffer memory the point "c" is ignored and the final intensity of the point is that of point "b", which is the point visible through the corresponding pixel.
One significant problem associated with the use of a BSP tree or of a conventional z-buffer is that the faces of the solid must be known. Since faces of the solid are not explicitly represented in the CSG tree they must be derived before they can be displayed. Such a derivation is known as a "boundary evaluation" and is a complex process which involves a large number of time consuming geometric calculations. Typically, the boundary evaluation process trims the faces of the primitive volumes by computing the solid's edges. Edges are computed by first generating curves, or pairwise intersections of surfaces, and then partitioning these curves accordingly to their intersections with all other primitive volume faces. Edges of the final solid are selected from this partition using the Boolean expression captured in the CSG tree. When a curve lies on more than two primitive faces, this selection may require an expensive evaluation of "edge-neighborhoods". It should be clear that, for objects involving hundreds of primitives, a boundary evaluation process implemented on a typical general purpose computer will be too slow for interactive use. Furthermore, the changing of a single parameter, such as a dimension or a position of a single primitive volume, may necessitate the recalculation of the entire boundary representation. The time required for such computation is a serious limitation on a user's ability to readily manipulate an object, such as is often required to correct mistakes in a design.
This boundary evaluation problem can be circumvented by employing a ray-casting algorithm, illustrated in FIG. 6, which computes lines, or rays, which pass through the viewpoint and the pixels of the screen model. Next the algorithm computes the intersection of each such ray with the solid. Along each ray a first intersection point, A, being the closest to the viewpoint, is selected and the surface hit by the ray at that point is used to compute the associated pixel color. Computing the intersection of the ray with the solid may be accomplished by first classifying the ray against each primitive volume by partitioning the ray into segments that are entirely in, on, or out of the primitive volume and then by merging the results of these classifications up-the-tree according to the Boolean operators associated with the nodes of that tree. These merging operations typically involve only numerical comparisons and logical operations. However, the process of partitioning the rays with respect to primitives requires line/surface intersection calculations, which become time consuming as the surfaces become more complex; these more complex surfaces corresponding to zeros of polynomials of higher degree. As such, known software implementations of ray-casting algorithms are too slow for interactive use.
In a scanline technique for each pixel all the rays for a given row of pixels are grouped and together they correspond to a horizontal row or line of the display screen. All rays for a given row need only be intersected with primitives whose images overlap with that particular row. The scanline method keeps track of the "active" primitives for the current row, the active primitives being those whose projection overlaps with the row. Rows on the screen are processed top-down, either one by one, or in relatively small groups of consecutive rows. A primitive enters the active list when its highest point lies on the row being processed. The primitive exits the active list when its lowest point is on the previously processed row. The highest and lowest points are determined using the coordinates of the projections of their vertices on the screen. For solids bounded by planar faces the highest and lowest points can be computed relatively easily. Also, efficient incremental methods may be used to compute the intersections of successive rays with any active face. Such scanline methods have been implemented for displaying boundaries of polyhedra. However, the computation of the solids boundary and its decomposition or approximation into planar faces is too slow to be performed at interactive rates with known scanline techniques.
In order to speed up the display process, specialized hardware systems have been developed. Initially such specialized systems implemented portions of the viewing transformation and scan conversion process with dedicated hardware. To further improve the performance, systems having parallel hardware architectures and employing pixel-parallel algorithms have been constructed wherein several processors operate on different image segments in parallel. The extreme of this approach is offered by a system that provides a small processor for each pixel of the display. So-called scanline systems offer an intermediate approach by providing a row of processors for one virtual scan line. After the generation of the pixel values, the values may be written directly to the video display, which requires that the values be generated at the video refresh rate, or the values may be stored in a frame buffer.
Such specialized hardware systems are generally substantially more costly and complex than a general purpose computer. Furthermore, these specialized systems by their nature do not address the problem of providing a fast and efficient method of shading CSG solids. Also, even for these specialized systems the aforementioned deficiencies in determining the faces and boundaries of a solid and in processing a CSG solid representation detrimentally impacts the speed of the system.
To avoid the complex and expensive calculations involved in the merging step of the above mentioned ray-casting algorithm, and to fully use the hardware support for face scan-conversion and for viewing transformations when displaying CSG solids, depth-buffer algorithms have been proposed (Goldfeather et al., Jansen). Thee algorithms convert the CSG tree into a sum-of-product (disjunctive) form, where each product is the intersection of solid primitives or of their complements. In these algorithms, points on the faces of each primitive are compared, using a depth-buffer, to all other primitives in the product. Points that are not on the product are rejected after one of these comparisons. Remaining points are processed for display using a depth-buffer to select the visible points.
This approach suffers from a significant deficiency in that products are rendered by comparing the depths of points of each primitive with all other primitives in the product. Such comparisons require a multiple scan-conversion of each primitive in each product. For example, when scan-converting a primitive A of a product ABCDE, the faces of B, C, D, and E must be scan converted to trim A to its visible contribution in the product ABCDE. Then, to scan-convert B, the remaining primitives C, D, and E must be scan-converted again in order to trim B to its visible contribution. This process is repeated until all primitives in the product are processed. In this example E is scan-converted five times.
Thus, a method that avoids the repeated scanning of the primitives in a product, such as a method wherein primitives in a product need only be scanned once to render a product, is a desirable goal. Furthermore, and has been made apparent, a need exists for a system and a method for rapidly and efficiently providing realistic shading for CSG represented solids and which also readily detect differences and interferences between such solids.